#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include "matching.h"
#include "preprocess.h"
#include "grouping.h"

// 添加 MIN 和 MAX 宏定义
#ifndef MIN
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#endif

#ifndef MAX
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#endif

// 初始化LCS矩阵
LCSMatrix* lcs_matrix_init(uint32_t rows, uint32_t cols) {
    LCSMatrix* matrix = malloc(sizeof(LCSMatrix));
    if (!matrix) return NULL;
    
    matrix->rows = rows;
    matrix->cols = cols;
    
    matrix->matrix = malloc(rows * sizeof(uint32_t*));
    if (!matrix->matrix) {
        free(matrix);
        return NULL;
    }
    
    for (uint32_t i = 0; i < rows; i++) {
        matrix->matrix[i] = calloc(cols, sizeof(uint32_t));
        if (!matrix->matrix[i]) {
            for (uint32_t j = 0; j < i; j++) {
                free(matrix->matrix[j]);
            }
            free(matrix->matrix);
            free(matrix);
            return NULL;
        }
    }
    
    return matrix;
}

// 释放LCS矩阵
void lcs_matrix_free(LCSMatrix* matrix) {
    if (!matrix) return;
    
    for (uint32_t i = 0; i < matrix->rows; i++) {
        free(matrix->matrix[i]);
    }
    free(matrix->matrix);
    free(matrix);
}

// 计算两个token序列的最长公共子序列长度
uint32_t lcs_length(const char** seq1, uint32_t len1, const char** seq2, uint32_t len2) {
    if (len1 == 0 || len2 == 0) return 0;
    
    LCSMatrix* matrix = lcs_matrix_init(len1 + 1, len2 + 1);
    if (!matrix) return 0;
    
    for (uint32_t i = 0; i <= len1; i++) {
        for (uint32_t j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                matrix->matrix[i][j] = 0;
            } else if (strcmp(seq1[i-1], seq2[j-1]) == 0) {
                matrix->matrix[i][j] = matrix->matrix[i-1][j-1] + 1;
            } else {
                matrix->matrix[i][j] = (matrix->matrix[i-1][j] > matrix->matrix[i][j-1]) ? 
                                      matrix->matrix[i-1][j] : matrix->matrix[i][j-1];
            }
        }
    }
    
    uint32_t result = matrix->matrix[len1][len2];
    lcs_matrix_free(matrix);
    
    return result;
}

// 计算两个token序列的相似度
double calculate_similarity(const char** tokens1, uint32_t len1, const char** tokens2, uint32_t len2) {
    // 计算模板长度（不包含变量标记和空格）
    uint32_t template_len = 0;
    for (uint32_t i = 0; i < len2; i++) {
        if (strcmp(tokens2[i], "<*>") != 0) {
            template_len++;
        }
    }
    
    if (template_len == 0) return 0.0;
    
    uint32_t lcs_len = lcs_length(tokens1, len1, tokens2, len2);
    double base_similarity = (double)lcs_len / template_len;
    
    // 添加惩罚项：如果长度差异过大，降低相似度
    double length_penalty = 1.0 - (fabs((double)len1 - (double)len2) / (len1 + len2));
    
    // 添加结构惩罚项：如果变量位置不匹配，降低相似度
    double structure_penalty = 1.0;
    
    // 粗略检查变量位置是否匹配
    for (uint32_t i = 0; i < MIN(len1, len2); i++) {
        if (strcmp(tokens1[i], "<*>") == 0 && strcmp(tokens2[i], "<*>") != 0) {
            structure_penalty -= 0.1;
        } else if (strcmp(tokens1[i], "<*>") != 0 && strcmp(tokens2[i], "<*>") == 0) {
            structure_penalty -= 0.1;
        }
    }
    
    structure_penalty = MAX(0.5, structure_penalty); // 确保不低于0.5
    
    // 综合相似度计算
    return base_similarity * length_penalty * structure_penalty;
}

// 在模板组中查找匹配的模板
MatchResult find_matching_template(const char** tokens, uint32_t token_count, 
                                  const char* group_key, void* template_group) {
    (void)group_key; // 避免未使用参数的警告
    
    MatchResult result = {false, -1, 0.0, NULL};
    
    // 将void*转换为TemplateGroup*
    TemplateGroup* group = (TemplateGroup*)template_group;
    
    if (!group || group->template_count == 0) {
        return result;
    }
    
    // 遍历所有模板，寻找匹配的模板
    for (uint32_t i = 0; i < group->template_count; i++) {
        if (!group->templates[i] || !group->templates[i]->template_str) {
            continue;
        }
        
        // 将模板字符串分词
        uint32_t template_token_count = 0;
        char** template_tokens = tokenize_template(group->templates[i]->template_str, &template_token_count);
        
        if (!template_tokens) {
            continue;
        }
        
        // 计算相似度
        double similarity = calculate_similarity(tokens, token_count, 
                                               (const char**)template_tokens, template_token_count);
        
        // 释放模板分词结果
        free_tokens(template_tokens, template_token_count);
        
        // 检查是否超过阈值
        if (similarity > SIMILARITY_THRESHOLD && similarity > result.similarity) {
            result.matched = true;
            result.template_index = i;
            result.similarity = similarity;
            result.matched_template = group->templates[i]->template_str;
        }
    }
    
    return result;
}

// 提取LCS序列（用于调试）
void extract_lcs_sequence(const char** seq1, uint32_t len1, const char** seq2, uint32_t len2, 
                          char*** result, uint32_t* result_len) {
    if (len1 == 0 || len2 == 0) {
        *result = NULL;
        *result_len = 0;
        return;
    }
    
    LCSMatrix* matrix = lcs_matrix_init(len1 + 1, len2 + 1);
    if (!matrix) {
        *result = NULL;
        *result_len = 0;
        return;
    }
    
    // 构建LCS矩阵
    for (uint32_t i = 0; i <= len1; i++) {
        for (uint32_t j = 0; j <= len2; j++) {
            if (i == 0 || j == 0) {
                matrix->matrix[i][j] = 0;
            } else if (strcmp(seq1[i-1], seq2[j-1]) == 0) {
                matrix->matrix[i][j] = matrix->matrix[i-1][j-1] + 1;
            } else {
                matrix->matrix[i][j] = (matrix->matrix[i-1][j] > matrix->matrix[i][j-1]) ? 
                                      matrix->matrix[i-1][j] : matrix->matrix[i][j-1];
            }
        }
    }
    
    // 提取LCS序列
    uint32_t lcs_len = matrix->matrix[len1][len2];
    char** lcs_seq = malloc(lcs_len * sizeof(char*));
    if (!lcs_seq) {
        lcs_matrix_free(matrix);
        *result = NULL;
        *result_len = 0;
        return;
    }
    
    uint32_t i = len1, j = len2, index = lcs_len;
    while (i > 0 && j > 0) {
        if (strcmp(seq1[i-1], seq2[j-1]) == 0) {
            lcs_seq[--index] = strdup(seq1[i-1]);
            i--;
            j--;
        } else if (matrix->matrix[i-1][j] > matrix->matrix[i][j-1]) {
            i--;
        } else {
            j--;
        }
    }
    
    lcs_matrix_free(matrix);
    *result = lcs_seq;
    *result_len = lcs_len;
}